public class Solution198 {
    public int rob(int[] nums) {
        int[] f=new int[nums.length];
        int[] g=new int[nums.length];
        f[0]=nums[0];
        g[0]=0;
        for (int i=1;i<nums.length;i++){
            f[i]=g[i-1]+nums[i];
            g[i]=Math.max(g[i-1],f[i-1]);
        }
        return Math.max(f[nums.length-1],g[nums.length-1]);
    }

    public static void main(String[] args) {
        System.out.println(new Solution198().rob(new int[]{1,2,3,1}));
    }
}
